The present invention relates to checking the integrity of digital data, and more particularly to a highly parallel cyclic redundancy code (CRC) generator that produces partial CRCs in parallel to any degree to greatly impact each and every high-speed digital networking application.
The cyclic redundancy code (CRC) has been used for a long time as a means to preserve the integrity of digital data for storage and transmission. Treating the data, or message, as a binary polynomial u(x), its CRC which corresponds to a particular generator polynomial g(x) may be generated by first raising the message polynomial to a proper power and then taking the remainder r(x) of the message polynomial divided by the generator polynomial. Early CRC implementations made use of the concept of linear feedback shift registers (LFSR) in which polynomial division is processed one bit at a time.
As the technology advanced single-bit CRC generation using LFSRs was not enough to handle high-speed data processing and transmission. Parallel CRC algorithms were then developed to meet this need. Most of these algorithms generate CRCs in software or in firmware, and some have been implemented in special hardware to take advantage of very large scale integrated (VLSI) circuit technology. These parallel CRC algorithms, although improved over single-bit LFSR, are not highly parallel in the sense that they can process at most one or two bytes at a time, limited by the degree of the generator polynomial. Byte-wise CRC generation is insufficient for very high-speed protocol processing in gigabit-per-second ATM/SONET environments. Considering the case where the internal data path of a host processor is 64-bit, it is highly desirable to perform 64-bit CRC generation even though the degree of the generator polynomial may only be 16 or 32. Existing CRC algorithms are cumbersome in this situation.
The key reason that existing CRC algorithms are limited in their degree of parallelism is deeply rooted in the concept of LFSRs. All existing algorithms try to solve the same problem, i.e., how to parallelize the bit-by-bit operation of LFSRs. As a result the degree of parallelism never goes beyond the perceived size of LFSRs.
What is desired is an improved, highly parallel CRC algorithm which can generate partial CRCs in parallel to any degree.